
package kuhnmunkresproject;

import java.util.LinkedList;


public class Matriz {
	private int[][] Mady;
        private int[][] Mm = null;
	private int[] S;
	private boolean complete;
        private boolean convex;
	
	public Matriz(int m){
		Mady = new int[m][m];
		complete = false;
	}
	
	
	public void GenerarGrafo(int[][] Mpesos){
            int m = Mady.length;
		for(int i = 0; i < m; i++)	
			for(int j = 0; j < m; j++)
				if(Mpesos[i][j] >= Mpesos[i][m] + Mpesos[m][j])
					Mady[i][j] = 1;
	}
	
	/*public void GenerarMatching(){
		int[][] M = new int[Mady.length][Mady.length];
		int [] s = new int[Mady.length];
		int count = 0;
		int ant = 0;
		boolean b = false;
		int p=0;
		for(int i = 0; i < Mady.length; i++)
		{	
			ant = count;
			for(int j = 0; j < Mady.length; j++)
			{
				if(Mady[i][j] == 1){
					b = true;
					for(int k = i-1; k>=0;k--){
						if(M[k][j] == 1)
							b = false;
					}
					if(b){
						M[i][j] = 1;
						count++;
						break;
					}	
				}
			}
			if(ant == count){
				s[p++] = i+1; 
			}
		}
                
		Mm = M;
                S = s;
		if(count == Mady.length)
			complete = true;
		else
			complete = false;
	}
         */
        public void GenerarMatching(int [][] Mpesos){
            int[][] M = new int[Mady.length][Mady.length];
            for(int i = 0; i < Mady.length; i++)
                    for(int j = 0; j < Mady.length; j++)
                            M[i][j] = Mady[i][j];
            int[] ij;
            for(int i = 0; i < Mady.length; i++){
                ij = Maximo(Mpesos, M);
                if(ij[0] == -1)
                    break;
                for(int j = 0;j < Mady.length;j++){
                    M[ij[0]][j] = 0;
                    M[j][ij[1]] = 0;
                    
                }
                M[ij[0]][ij[1]] = 2;
                
            }
            int m = M.length;
		for(int i = 0; i < m; i++){
                    for(int j = 0; j < m; j++){
                        if(M[i][j] == 2)
                            M[i][j] = 1;
                    }
                }	
            Mm = M;
            ImprimirMatriz(Mm);
            CalcularS();
        }
       
        /*
        public void GenerarMatching(int [][] Mpesos){
            HungarianAlgorithm hun = new HungarianAlgorithm();
            int[][] MpesosTemp = Mpesos.clone();
            
            int[] resultado = hun.FindAssignments(MpesosTemp);
            int[][] resultadoMatriz = new int[resultado.length][resultado.length];
            
            for(int i = 0; i < resultado.length; i++){
                //System.out.print(resultado[i] + " , ");
                resultadoMatriz[i][resultado[i]] = 1;
            }
            
            Mm = resultadoMatriz;
            ImprimirMatriz(Mm);
            CalcularS();
        } */
        
        public void CalcularS(){
            int [] s = new int[Mady.length];
            boolean flag;
            int p = 0;
            for(int i= 0; i< Mm.length;i++){
                flag = true;
                for(int j= 0; j< Mm.length;j++){
                    if(Mm[i][j] == 1){
                        flag = false;
                        break;
                    } 
                }
                if(flag){
                    s[p++] = i+1;
                }
            }
            S = s;
            if(s[0] == 0)
			complete = true;
            else
			complete = false;
        }
        
        public int[] Maximo(int[][] Mpesos, int [][] Mad){
            int max = Integer.MIN_VALUE;
            int[] ij = new int[2];
            boolean b = true;
            for(int i = 0; i < Mady.length; i++){
                for(int j = 0; j < Mady.length; j++){
                    if(max < Mpesos[i][j] && Mad[i][j] == 1){
                        ij[0] = i;
                        ij[1] = j;
                        max = Mpesos[i][j];
                        b = false;
                        
                        //this.ObtenerIguales(j, ij, max, i, j, Mpesos, Mad);
                    }
                }
            }
            if(b){
                ij[0]=-1;
                ij[1]=-1;
            }
            else{
                this.ObtenerIguales(ij[1], ij, max, ij[0], ij[1], Mpesos, Mad);
            }
            return ij;
        }
        
        public void ObtenerIguales(int renI, int[] ij, int max, int i, int j, 
                int[][] Mpesos, int[][] Mad){
            
            LinkedList<Integer> Iguales = new LinkedList<Integer>();
            
            for(int k = i + 1; k < Mady.length; k++){
                if(max == Mpesos[k][j] && Mad[k][j] == 1){
                    Iguales.add(k);
                    
                    if(CompararEfectividad(Mpesos, i, k))
                    {
                        ij[0] = k;
                        ij[1] = j;
                    }
                }
            }
            
            
            /*
            for(int m = 0; m < Iguales.size(); m++){
                for(int l = m + 1; l < Iguales.size(); l++){
                    // Comparar
                    if(CompararEfectividad(Mpesos, Iguales.get(m), Iguales.get(l)))
                    {
                        ij[0] = Iguales.get(l);
                        ij[1] = j;
                    }
                }
            }
            
            
            for(int k = i + 1; k < Mady.length; k++){
                if(max == Mpesos[k][j] && Mad[k][j] == 1){
                    // Comparar
                    if(CompararEfectividad(Mpesos, i, k))
                    {
                        ij[0] = k;
                        ij[1] = j;
                    }
                }
            }*/
        }
        
        public boolean CompararEfectividad(int[][] Mpesos, int renA, int renB){            
            int contA = 0, contB = 0, acumA = 0, acumB = 0;
            
            for(int i = 0; i < Mady.length; i++){
                if(Mm!=null){
                    if(Mm[renA][i] != 1 && Mm[renB][i] != 1)
                    {
                        if(Mpesos[renA][i] > Mpesos[renB][i]){
                            contA++;
                            acumA+=Mpesos[renA][i];
                            
                        }
                        else if(Mpesos[renA][i] < Mpesos[renB][i]){
                            contB++;
                            acumB+=Mpesos[renB][i];
                        }
                    }
                }
            }
            
            if(contB < contA){
                return true;
            }
            else if(contB == contA)
            {
                if(acumB < acumA)
                {
                    return true;
                }
            }
            
            return false;
        }

	public boolean IsComplete(){
		return complete;
	}
	
        public LinkedList VecinosAdyacencia(int i){
            LinkedList<Integer> v = new LinkedList<Integer>();
            int k = 0;
            i--;
            for(int p = 0; p < Mady.length; p++){
                if(Mady[i][p] == 1)
                    v.add(p+1);
            }
            return v;
        }
        
        public int VecinosMaching(int i){
            
            int k = 0;
            i--;
            for(int p = 0; p < Mm.length; p++){
                if(Mm[p][i] == 1)
                  return p+1;
            }
            return -1;
        }
        
	public int[] NoSaturados(){
		return S;
	}
        
        public int[][] getMatrizAdyacencia(){
            return Mady;
        }
	
        public int[][] getMatrizMatchig(){
            return Mm;
        }
        
        public void setMatrizMatchig(int[][] NuevoMatching){
            Mm = null;
            Mm = NuevoMatching.clone();
        }
        
        public void ImprimirMatriz(int [][] M){
            int m = M.length;
		for(int i = 0; i < m; i++){
                    for(int j = 0; j < m; j++){
                        System.out.print(M[i][j] + " ");
                    }
                    System.out.print("\n");
                }	
                System.out.println();
        }
        
        public void getComponentes()
        {
            LinkedList<Integer> leidos = new LinkedList<Integer>();
            int actual = 0;
            boolean ban = false, ban2 = true;
            
            convex = true;
            
            while(ban2)
            {
                ban2 = false;
                
                for(int i = 0; i < this.Mady.length; i++)
                {
                    if(this.Mady[actual][i] == 1)
                    {
                        ban = false;

                        for(int j = 0; j < leidos.size(); j++)
                        {
                            if(leidos.get(j) == i)
                            {
                                ban = true;
                            }
                        }

                        if(!ban)
                        {
                            leidos.add(actual);
                            actual = i;
                            ban2 = true;
                            break;
                        }
                    }
                }
            }
            
            if(leidos.size() == this.Mady.length)
            {
                this.convex = true;
            }
            else
            {
                this.convex = false;
            }
        }
        
        public boolean IsConvex(){
		return convex;
	}
}
